package sy6_Behavioral_Pattern.interpreter;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
 * 功能：做若干整数的加、减、乘、除和幂运算，如计算1+2*3-32/2^3
 * 把单元指令集组成一个树结构，称之为抽象语法树（Abstract Syntax Tree，AST）。
 * 按照将来需要解释的顺序，优先执行的指令放在树的叶的位置，最后执行的指令是树根Root。
 */

class Node { //表示二叉树结点
	private Expression expression; //结点数据（抽象类型）
	private Node left;  //自身类型（左指针）：左结点
	private Node right; //自身类型（左指针）：右结点

	public Node(Expression expression) {  //构造方法
		this.expression=expression;
		left=null; 
		right=null;  
	}
	public Expression getExpression() {  //getter
		return expression;
	}
	public Node getLeft() {
		return left;
	}
	public void setLeft(Node left) {
		this.left=left;
	}
	public Node getRight() {
		return right;
	}
	public void setRight(Node right) {
		this.right=right;
	}
}

abstract class Expression{ //角色1：抽象表达式 Expression 表示结点
    //解析方法；参数为二叉树根结点；返回值类型为int
	abstract public int interpret(Node root);
}

class NumExpression extends Expression{ //角色2：终结符表达式继承抽象类
    private int value;  //数值数据

    public NumExpression(int value){  //构造方法
        this.value=value;
    }
    public int getValue() {
		return value;
	}

	@Override
	public  int interpret(Node root){   //解析终结表达式（运算数结点）
        return ((NumExpression)(root.getExpression())).getValue();  //取属性、类型强转、再取属性值
    }
}

class OpExpression extends Expression{  //角色3：非终结符表达式，表示运算符，需考虑运算优先级；继承抽象类
    private Op value;  //类属性为枚举Op类型
    private static int calOrder=0;  //计算序号，测试用
    public OpExpression(Op value){  //构造器
        this.value=value;
    }
    public Op getValue() {
		return value;
	}
    public Prioirty getPrioirty() {  //返回枚举成员对应的优先级
        switch(value) {
        case Plus:
        case Minus:
            return Prioirty.Lv1;
        case Multiply:
        case Divide:
            return Prioirty.Lv2;
        case Power:
            return Prioirty.Lv3;            
        default:
            return Prioirty.Lv0;
        }
    }

	@Override
    public  int interpret(Node root){  //解析非终结表达式（运算符结点）
        int lvalue, rvalue;
        if(root.getLeft()==null)
            lvalue=0;
        else  //解析器方法递归计算左结点数据
            lvalue=(root.getLeft().getExpression()).interpret(root.getLeft());
        if(root.getRight()==null)
            rvalue=0;
        else  //解析器方法递归计算右结点数据
            rvalue=(root.getRight().getExpression()).interpret(root.getRight());
        switch(((OpExpression) root.getExpression()).getValue()) {  //根据运算符得到相应的返回值
	        case Plus:
	        	calOrder++; System.out.println("第"+calOrder+"次计算："+lvalue+"+"+rvalue+"="+(lvalue+rvalue));//测试
	            return lvalue+rvalue;
	        case Minus:
	        	calOrder++; System.out.println("第"+calOrder+"次计算："+lvalue+"-"+rvalue+"="+(lvalue-rvalue));
	            return lvalue-rvalue;
	        case Multiply:
	        	calOrder++; System.out.println("第"+calOrder+"次计算："+lvalue+"*"+rvalue+"="+(lvalue*rvalue));//测试
	            return lvalue*rvalue;
	        case Divide:
	        	calOrder++; System.out.println("第"+calOrder+"次计算："+lvalue+"/"+rvalue+"="+(lvalue/rvalue));//测试
	            return lvalue / rvalue;
	        case Power:
	        	calOrder++; System.out.println("第"+calOrder+"次计算："+lvalue+"^"+rvalue+"="+(int)Math.pow(lvalue,rvalue));//测试
	            return (int)Math.pow(lvalue,rvalue);
	        default:
	            return 0;
        }
    }
}

class Context { //角色4：环境类Context，根据运算表达式构建其抽象语法树。
	private Node root;  //语法树根结点
    public Context(String exp) {  //有参构造方法：先切分字符:（词法分析），后形成语法树（语法分析）
        List<Expression> expressions = ExpressionTokenizer.token(exp);
        for(Expression e:expressions) {
        	append(e);  //添加表达式结点至语法树AST
        }
    }
	public Node getRoot(){  //getter
		return root;
	}
	public void append(Expression expression){ //添加（表达式）结点
		root=append(root,expression);  //调用私有的重载方法：刷新树的根结点
	}
	private Node append(Node root, Expression expression){  //返回语法树根结点
		if(root==null) { return new Node(expression); }
		if(expression instanceof NumExpression) {  //添加操作数
			if(root.getExpression() instanceof OpExpression) {  //如果根结点为运算符
				if(root.getRight()==null) {  //如果右子树为空
					Node newNode=new Node(expression);
					root.setRight(newNode); //直接添加为右结点
					return root;
				} else {  //如果右子树不为空（在添加了较高优先级的运算符时）
					Node node=append(root.getRight(),expression);  //添加右子树
					root.setRight(node);  //作为右子树的右结点
					return root;
				}
			}
		}else{  //添加运算符
			if(root.getExpression() instanceof NumExpression) {  //如果根结点为操作数
				Node newRoot=new Node(expression);  //创建新的运算符结点
				newRoot.setLeft(root); //操作数作为新结点的左端
				return newRoot;  //作为新的根结点
			}else{  //如果根结点为运算符，需要考虑优先级
				OpExpression expression1=(OpExpression)expression;  //拟新增结点
				OpExpression expression2=(OpExpression)root.getExpression();  //已经存在的根结点
				//若新的运算符优先级不超过根结点，则将新运算符作为新的根结点，原根加到左端
				if(expression1.getPrioirty().getValue()<=expression2.getPrioirty().getValue()){
					Node newRoot=new Node(expression1);
					newRoot.setLeft(root);
					return newRoot;
				}else{  //新的运算符优先级高于当前根结点，则需要优先运算、添加到当前根结点的新增右子树
					//原根结点的右孩子作为新增右子树的左孩子
					Node node=append(root.getRight(),expression);
					root.setRight(node);
					return root;
				}
			}
		}
		return null;
	}
}
class ExpressionTokenizer {  //表达式切分者工具类：将字符串切分为 Expression序列（单元指令）。
	public static List<Expression> token(String expStr) {
        List<Expression> list=new ArrayList<>();  //存放整个表达式
        List<Character> temp=new ArrayList<>();  //运算数对应的数字字符序列列表
        for(int i=0; i<expStr.length();i++){  //按字符扫描运算表达式
            char ch=expStr.charAt(i);
            if(ch>='0' && ch<='9'){  //数字
                temp.add(ch);
            }else{  //运算符
                if(temp.size()>0) {  //遇到运算符时，需要处理 temp中存放的数字字符序列为一个运算数
                    int num=Integer.parseInt(NumCharToString(temp));
                    Expression expression1=new NumExpression(num);
                    list.add(expression1);  //先添加数据
                    temp.clear(); //清空运算数字符列表
                }
                OpExpression expression2=new OpExpression(Op.getValue(ch));
                list.add(expression2);   //后添加运算符
            }
        }
        if(temp.size()>0) {  //需要处理最后一个运算数
            int num=Integer.parseInt(NumCharToString(temp));
            Expression Expression=new NumExpression(num);
            list.add(Expression);
            temp.clear();
        }
        return list;
    }
    private static String NumCharToString(List<Character> list) {  //组合运算数的数字系列形成一个字符串
        StringBuilder builder=new StringBuilder(list.size());
        for(Character ch:list) {
            builder.append(ch);
        }
        return builder.toString();
    }
}

enum Op{   //定义运算符枚举类型
    Plus('+'),Minus('-'),Multiply('*'),Divide('/'),Power('^');  //枚举成员
    char value;
    Op(char value) {  //有参构造方法
        this.value = value;
    }

    static Op getValue(char ch) {  //根据四则运算符得到枚举类型的枚举成员【静态方法；参数为char类型】
        switch (ch) {
        case '+':
            return Plus;
        case '-':
            return Minus;
        case '*':
            return Multiply;
        case '/':
            return Divide;
        case '^':
            return Power;
        default:
            return null;
        }
    }
}
enum Prioirty{   //优先级枚举类型
    Lv3(3),Lv2(2), Lv1(1), Lv0(0);
    int value;
    Prioirty(int value) {  //有参构造方法
        this.value = value;
    }
    int getValue() {  //获取枚举成员对应的枚举值【无参，返回int类型】
        return value;
    }
}

public class Client {  //客户端，同时关联于Expression和Context
    public static void main(String[] args) throws Exception {
        System.out.print("请输入要计算的四则运算表达式：");
        Scanner scanner = new Scanner(System.in);
        String expStr = scanner.nextLine();
        scanner.close();
        //String expStr=(new BufferedReader(new InputStreamReader(System.in))).readLine();
        Context context=new Context(expStr);  //构建语法树；体现Client对Context的关联
        Expression rootExpression=context.getRoot().getExpression();  //获取根结点数据
        int result=rootExpression.interpret(context.getRoot());  //解释语法树，参数为根结点
        System.out.println("整个表达式计算结果："+result);
    }
}